package Sort.面试;

public class ArrayTopN {
    /**
     * 交换
     * @param arr
     * @param index1
     * @param index2
     */
    public static void swap(int[] arr, int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    /**
     * 从最后一个子节点的父节点，一次创建小顶堆
     * @param arr
     */
    public static void buildHeap(int[] arr){
        int length = arr.length;
        for(int i = length/2-1; i >= 0; i--){
            swapHeap(arr,i,length);
        }
    }

    /**
     * 创建大顶堆
     * @param arr
     * @param start
     * @param end
     */
    public static void swapHeap(int[] arr, int start, int end){
        int left = 2 * start + 1;
        int right = 2 * start + 2;
        int max = start;
        if(left < end && arr[left] < arr[max]){
            max = left;
        }
        if(right < end && arr[right] < arr[max]){
            max = right;
        }
        if(max != start){
            swap(arr, start, max);
            swapHeap(arr, max, end);
        }
    }

    public static int[] getArrayTopN(int[] arr, int n){
       if(arr == null){
           return null;
       }
       int length = arr.length;
       if(length == 0 || n >= length){
           return arr;
       }
       int arrTop[] = new int[n];
       for(int i = 0; i < n; i++){
           arrTop[i] = arr[i];
       }
       //依次创建大顶堆
        buildHeap(arr);
       for(int i = n; i < length; i++){
           if(arrTop[0] < arr[i]){
               arrTop[0] = arr[i];
               swapHeap(arrTop, 0, n);
           }
       }
       return arrTop;
    }


    public static void main(String[] args) {
        int length = 100000000;
        int[] arr = new int[length];

        for(int i = 0; i < length; i++){
            arr[i] = i;
        }

        int n = 10;

        long start = System.currentTimeMillis();

        int[] topN = getArrayTopN(arr,n);

        long end = System.currentTimeMillis();
        System.out.println(end - start);

        for(int i = 0; i < n; i++){
            System.out.println(topN[i]);
        }
    }


}
